import java.util.ArrayDeque;
import java.util.Deque;

public class Day12 {
    // 394、字符串解码
    public String decodeString(String s) {
        // 使用栈进行解决
        Deque<StringBuilder> st = new ArrayDeque<>(); // 存放字符串
        // 先往里面存放一个空字符串，用于最后返回的数据
        st.push(new StringBuilder());
        Deque<Integer> nums = new ArrayDeque<>(); // 用于存放数字
        int i = 0,n = s.length();
        char[] ss = s.toCharArray();
        // 遍历字符串
        while(i < n) {
            if(ss[i] >= '0' && ss[i] <= '9') {
                int tmp = 0;
                // 数字并不是单个，可能是多位，如：123
                while(i < n && ss[i] >= '0' && ss[i] <= '9') {
                    tmp = tmp * 10 + (ss[i] - '0');
                    i++;
                }
                nums.push(tmp);
            }else if(ss[i] == '[') {
                // 把这个符号后面的字符串提取出来，放入到栈中，并且要是创建一个新的 StringBuilder放入到栈中
                i++;
                StringBuilder tmp = new StringBuilder();
                while(i < n && ss[i] >= 'a' && ss[i] <= 'z') {
                    tmp.append(ss[i]);
                    i++;
                }
                st.push(tmp);
            }else if(ss[i] == ']') {
                // 说明对应的字符已经放完了，并且对应的数字已经放入栈中，取出，并进行处理，放入原栈顶的后面的 StringBuilder 中
                int k = nums.pop();
                StringBuilder tmp = st.pop();

                while(k-- != 0) {
                    st.peek().append(tmp);
                }
                i++;
            }else {
                // 如果遇到单个 字符串 的话，直接放入到 栈顶中
                StringBuilder tmp = new StringBuilder();
                while(i < n && ss[i] >= 'a' && ss[i] <= 'z') {
                    tmp.append(ss[i]);
                    i++;
                }
                st.peek().append(tmp);
            }
        }
        // 上述代码处理结束之后，st 这个栈中的最后的栈顶中的数据就是最后返回的值
        return st.peek().toString();
    }
}
